package lcof;

import pojo.Node;

import java.util.HashMap;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: CopyRandomList35
 * @description: 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/5/1014:08
 * @since V1.0
 */
public class CopyRandomList35 {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node t = head;
        //遍历放入map
        while (t!=null){
            Node node = new Node(t.val);
            //key为旧链表的节点，value为新节点，该新节点还没有next和random指针
            map.put(t,node);
            t = t.next;
        }
        Node p = head;
        while (p!=null){
            Node node = map.get(p);
            node.next = map.get(p.next);
            node.random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}
